#include <iostream>
using namespace std;

/**
 * 24 
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
class SwapNodes{
public:
    ListNode* swapPairs(ListNode* head) {
      // 设置虚拟头结点
	  ListNode* dummyHead = new ListNode(0);
	  dummyHead->next = head;

	  ListNode* p = dummyHead;	// 交换对前一个节点
	  while(p->next && p->next->next){
		// 获取要交换的两个节点
		ListNode* node1 = p->next;
		ListNode* node2 = node1->next;
		// 存储这队节点之后的节点
	    ListNode* next = node2->next;	// 一定存在，最差为NULL
		
		// 交换节点
		node2->next = node1;
		node1->next = next;
		p->next = node2;
		p = node1;				// node1 node2已经交换位置
	  }	

	  ListNode* retHead = dummyHead->next;
	  delete dummyHead;
	  return retHead;	
    }

};


int main(){

}
